package binarysearchtree;

public class BinarySearchTree {

    static class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root = null;

    public boolean search(int val){
        TreeNode cur = root;

        while (cur!=null){
            //大于去右边
            if(val>cur.val){
                cur = cur.right;
            }else if(val<cur.val){
            //小于去左边
                cur = cur.left;
            }else{
            //相等返回true
                return true;
            }

        }
        return false;
    }

    public boolean insert(int val){
        TreeNode insert = new TreeNode(val);

        if(root==null){
            root = insert;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        while (cur!=null){
            if(val>cur.val){
                parent = cur;

                cur = parent.right;

            }
            else if(val<cur.val){
                parent = cur;

                cur = parent.left;

            }
            else{
                return false;
            }
        }

        if(val>parent.val){
            parent.right = insert;
        }else{
            parent.left = insert;
        }
        return true;
    }

    //插入结点

    public boolean insert2(int val){
        TreeNode insert = new TreeNode(val);

        if(root==null){
            root = insert;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;

        while (cur!=null){
            parent = cur;
            if(val>cur.val){
                cur = cur.right;
            }
            else if(val<cur.val){
                cur = cur.left;

            }
            else{
                return false;
            }
        }

        if(val>parent.val){
            parent.right = insert;
        }else{
            parent.left = insert;
        }
        return true;
    }

    //删除结点
    public void remove(int val){

        TreeNode cur = root;
        TreeNode parent = null;
        //先找到删除结点的位置
        while (cur!=null){
            if(val>cur.val){
                parent = cur;
                cur = cur.right;

            }
            else if(val<cur.val){
                parent = cur;
                cur = cur.left;

            }
            else{
                delete(parent,cur);
            }
        }
    }

    private void delete(TreeNode parent,TreeNode cur){
        //第一种情况，左子树为空
        if(cur.left==null){
            //1.等于根结点
            if(cur==root){
                root = cur.right;
            }
            //2.位于根结点的左边
            else if(cur==parent.left){
                parent.left = cur.right;
            }
            //3.位于根结点的右边
            else{
                parent.right = cur.right;
            }
        }
        //第二种情况，右子树为空
        else if(cur.right==null){

            if(cur==root){
                root = cur.left;
            }
            else if(cur == parent.left){
                parent.left = cur.left;
            }
            else{
                parent.right = cur.left;
            }
        }
        //第三种情况，左，右子树都为空
        //替罪羊的思路，先找到适合放到要删除结点的目标结点，然后将目标覆盖要删除的结点，再删除替罪羊
        else{
            TreeNode targetparent = cur;
            //这里要么去左边然后一直往右边走，要么去右边然后一直往左边走
            TreeNode target = cur.right;

            while (target.left!=null){
                targetparent = target;
                target = target.left;
            }
            //覆盖cur，然后删除替罪羊即target
            cur.val = target.val;

            if(target == targetparent.left){
                targetparent.left = target.right;

            }else if(target == targetparent.right){ //这里的判断是预防target一开始选定往右走时就已经找到了替罪羊，
                                                    // 根本就没有进while循环
                targetparent.right = target.right;
            }

        }


    }

}
